In both the military and commercial market places, there is an ever expanding use of radio-based geolocation/navigation devices (systems and methods described in this disclosure can be applied to both geolocation and navigation and are used interchangeably). Though they generally perform satisfactorily, in virtually every application there are instances where degraded accuracy or non-availability create dangerous situations. For military applications, degraded positional accuracy due to jamming can affect the safety of troops or the navigation precision of a guided weapon. For commercial applications, the non-availability of GPS service inside a building can delay the arrival of emergency personnel to a 911 caller in distress.
Historically, much research has been done to improve the performance of GPS user equipment, yielding great gains in positional accuracy and availability. These activities have principally focused on improving the traditional functions in user equipment such as receiver sensitivity, reference oscillator stability, correlator speed, and signal processing algorithm performance. To create opportunities for future large gains in performance, new approaches and algorithms will need to be applied to user equipment including aiding using other RF signals of opportunity. Therefore, this disclosure represents a means to provide large gains in geolocation and navigation performance vs. diminishing incremental benefits from traditional GPS user equipment research topics. The goal is to be able to maintain the same level of accuracy as a GPS in GPS-denied environments, without adding significant system complexity, cost, or operational burdens. These gains can benefit the growing markets and applications in both the military and commercial sectors.
The use of Signals of Opportunity (SoOPs), such as TV broadcasts and satellite-based communications networks present a very promising solution toward providing a ubiquitous navigation solution in all environments. There are a plethora of RF signals that easily penetrate into what are considered to be GPS-obstructed or impaired scenarios, where impairment is due to either due to signal path loss or jamming. Some of these SoOPs are not only very high power relative to GPS, but offer excellent time resolution to enable precision location due to wide transmission signal bandwidth. It is fairly straightforward to see how through the use of many of these signals, there is a tremendous potential toward a robust and essentially jam-proof navigation solution. There are, however, some associated challenges. Two candidate methods for location and navigation are obvious choices: timing measurement based systems, and signal power level based measurement systems.
With respect to timing measurements, most SoOPs are RF signals whose purpose are not for navigation, but for information transmission, and may therefore not be well suited for use in geolocation/navigation without addressing their deficiencies. For example, most SoOPs are not synchronized to a common time source, as this may not be a requirement for their intended use. Without a timing reference, a measured time of arrival is not a useful measurement unless it can be paired with a time of transmission from which a propagation distance can be derived. Time of transmission, in this context, is the precise time at which a SoOP radiates through the transmit antenna. Time differences (leading to hyperbolic surfaces of position) between multiple observed SoOPs are also not useful unless the transmit timing relationship between the SoOPs is either known or derived through measurements made at known locations. Most SoOPs operate with low stability reference oscillators, which enable low-cost communications, but pose a challenge when used for navigation. Furthermore, many SoOPs may not even be digital signals and are therefore more difficult to use for navigation. These, and other factors, pose serious technical challenges for using SoOPs in precision navigation.
As stated previously, power-based measurements are also possible on SoOP sources. Some commercial success has been experienced using measured power levels of SoOPs such as cellular phone and WiFi for location estimation. These techniques are suitable for areas in which there is a very high density of cell towers or access points relative to the area in which location is to be estimated. For high-precision systems, the navigation coverage area must be extensively calibrated prior to use and is therefore not considered to be a viable candidate technique for broad area navigation and geolocation. Another method uses an even simpler mechanism whereby coarse coverage areas are measured through drive testing and mapped by what WiFi access points are visible as a function of position (such as Skyhook Wireless). This technique has several significant weaknesses that disqualify it for use as a candidate solution as a high precision solution. Drive testing is not considered to be a viable requirement due to the immense operational burden is carries. Furthermore, the accuracy of such a solution is generally on the order of the coverage footprint of the WiFi access point which could be on the order of tens to hundreds or meters or more, which exceeds the target goal of GPS-grade accuracy. If no access points are detected (WiFi is not even close to providing ubiquitous worldwide coverage) then the method will not work at all. Access points, while intended for fixed use, can be easily moved, replaced, or disabled, and make for an unreliable signal source if the surveyed positions are critical to the solution. Other WiFi positioning systems that have been explored are location through the built-in ranging mechanisms within the WiFi protocol. Specifically, range determination is made through calculation of the mean round trip time delay of packets in the data/acknowledgement sequence. Academic researchers have reported promising results using unmodified WLAN chipsets, however questions remain as to how sensitive the techniques are to different manufacturers and performance in high multipath areas.
A significant amount of prior art exists around the fields of geolocation and navigation. Prior art inertial measurement systems thoroughly describe using mechanical methods, often called “dead reckoning”, to position and navigate. Devices such as gyroscopes, wheel encoders (odometers), and accelerometers (collectively referred to as inertial measurement units (IMU)) have been used, and generally operate by determining a position relative to a known location or starting point as a body moves over time. An IMU typically consists of accelerometers to measure local accelerations and gyros to measure local rotation rates. The IMU position and velocity is obtained by integrating the IMU measurements. Strapdown micro-electro-mechanical sensor (MEMS) IMUs are particularly attractive due to their size weight and power. MEMS IMUs are electrically driven, miniature mechanical structures produced by micro-machining techniques. In the case of silicon-based MEMS, the micro-machining is performed using standard integrated circuit (IC) fabrication techniques. In this way silicon-based MEMS fully leverage the existing IC industry, enabling the mass production of precision devices.
It is important to understand the units used to express the error terms in these inertial measurement devices. For example, accelerometer errors are expressed in Random Walk Units, such as acceleration per square root frequency or velocity per square root time. A Random Walk Error expressed in m/s per √hour can be converted to m/s2 per √Hz by dividing it by 60.
                              1          ⁢                                    m              ⁢                              /                            ⁢                              s                2                                                    Hz                                      =                              1            ⁢                                                                                m                    2                                    ⁢                                      /                                    ⁢                                      s                    4                                                                    1                  /                  s                                                              =                                    1              ⁢                                                                                                                  m                        2                                            ⁢                                              /                                            ⁢                                              s                        2                                                              s                                    ×                                                            3600                      ⁢                                                                                          ⁢                      s                                                              1                      ⁢                                                                                          ⁢                      hr                                                                                            =                          60              ⁢                                                          ⁢                                                m                  ⁢                                      /                                    ⁢                  s                                                  hr                                                                                        [        1        ]            
Similarly Gyroscope Random Walk Errors are generally expressed in the form of angular rate per square root frequency or angle per square root time. Converting from deg/√hour to deg/s per √Hz simply requires dividing it by 60. It is important to note that as sample rate increases, the error decreases. Also, in addition to Random Walk Errors, another term used to characterize IMU performance is noise. These errors are represented in the equation below:gr=r+cr+br+wgyro  [2]Where cr is the constant offset, r is the rotational rate, br is the walking bias, and wgyro is the wideband sensor noise. Left unbounded, internally generated errors will eventually accumulate and degrade the navigation performance of all IMUs to a level that is unusable for high accuracy navigation and position. There is also a large variation in performance of IMUs depending on their target application. For example, FIG. 1(a) shows the position error of a tactical IMU as a function of time and FIG. 1(b) shows the position error of a consumer grade IMU as a function of time. In terms of longitudinal error, the consumer grade IMU demonstrates over thirty times the error when compared to the tactical grade IMU over the same period of time.
For this reason, IMUs are best used in conjunction with other measurements sources that have independent error sources, and offer a way to correct the IMU through measurement of absolute position in order to bound the IMU error build up. The use of algorithm techniques such as Kalman filtering provides a convenient and robust way of fusing these disparate measurement sources together to construct an optimized navigation model.
Another well-known field in geolocation and navigation is radio-waved based and includes radio direction finding and geolocation (time difference of arrival, time of arrival, received power level, etc.) using positioning-specific RF sources such as the earth's magnetic field, LORAN, GPS, and GNSS.
The Global Positioning System (GPS) is an excellent example of radio-based geolocation. It provides for worldwide availability and precision geolocation when a clear view to the sky is available. However, due to limited transmitter power and the extremely long propagation distance between the GPS satellites and users on the earth's surface (ranging approximately 20,192-25,785 km), the received signals are quite weak and pose a significant reception challenge when the signal is further obstructed due to atmospheric loss, building penetration loss and intentional or unintentional interference sources. At the L1 frequency, two types of codes are used: the C/A code and the P code, which can be encrypted by the Y code (referred to as the P(Y) code). In order to compute location, the GPS receiver must first acquire the satellite signals either through the acquisition of the C/A code, or directly through the P(Y) code. In general, it is desirable to use the C/A code for acquisition due to its shorter sequence length and therefore significantly faster acquisition time when the GPS receiver is in what is referred to as a cold-start or start-up from an unknown location and time. In an un-aided mode, the 50 bps navigation data bits must also be recovered in order to decode the required payload of telemetry, ephemeris, and satellite almanac information.
In standalone, un-assisted mode, GPS sensitivity can be addressed in several ways. One way is to increase the antenna gain through larger physical antennas, directional antennas, smart beam-steering techniques, etc. These have disadvantages due to the added size, cost, weight, and power requirements. Other techniques have been developed to improve acquisition and demodulation sensitivity through improved radio components and signal processing advances.
Assisted GPS, or A-GPS was a technique that was propelled into mass use by the US FCC E911 requirement to locate emergency callers from mobile phones. The main principle behind A-GPS is two-fold: to significantly speed GPS acquisition time from a cold-start, and to improve GPS sensitivity in weak signal conditions. Acquisition speed is improved by exploiting a coarse knowledge of the location of the GPS device along with the time of day, to predict what satellite signals should be in view and what their respective code phases and Doppler frequency shifts should approximately be. This results in a dramatically reduced search space for the A-GPS device when attempting to acquire the satellite signals and subsequently reduces the processing time. Improved GPS signal sensitivity is enabled by alleviating the need to demodulate the navigation data. This allows for the computation of pseudo-range estimates from only the acquisition of the C/A code, which requires less received signal strength than if the GPS receiver had to also decode the navigation data payload. Furthermore, longer C/A code integration times, and therefore higher processing gain is achievable when the assistance information forwards the navigation data to the GPS handset. Once the navigation data is known, the phase transitions that occur due to the data modulation can essentially be removed and allow for coherent integration periods that exceed a bit interval. The pseudo-range measurements are fused with atmospheric corrections and the satellite ephemeris, either locally on the GPS receiver or at a remote server, and a high-precision GPS solution is computed.
FIG. 2 shows a diagram of the required infrastructure in a typical commercial wireless A-GPS network. Coarse location is derived from the knowledge of which base station 200 is currently serving the mobile device 210 requesting location service. Based on this coarse location, the appropriate assistance data 220 is routed from the network to the mobile device 210 over the communications link established between the base station and the mobile. Depending on the network configuration, either the mobile or the network can compute the final location.
Radio direction finding and geolocation methods have also been described that use other known non-positioning-specific RF sources but rely on knowledge of the transmitter location and timing relationships between sources. Navigation and geolocation using combinations of RF sources in hybrids where location estimate is based on combining measured surfaces of position are also well-known. Methods and systems removing the limitation of requiring knowing timing relationships between RF sources by adding reference timing stations are also well known. For example, US Pat Pub. No. 2009233621 describes a location method and system that does not require time synchronization between radio sources, but include many limitations on the RF sources, measurements made and inter-element communications channel content. The described methods require that the time of transmission of a radio synchronization signal be transmitted as part of the emission to be received by another element in the system. In other described embodiments, specific relationships exist between system elements (i.e. members of s wireless local area network (WLAN), or transmission of specific synchronization signals). With respect to cellular systems, this application describes a “PhaseNet” approach where requirements are placed on the network elements such as inclusion of special ZT nodes (a type of reference station), being part of the cellular network, use of cellular-specific synchronization signals, known location for the ZT nodes, and others.
Extensions of location methodologies to optical sources (landmarks), including extensions to discovery of unknown optical landmarks and simultaneous location and mapping (SLAM) techniques are also well known.
Another specific set of prior art has been published in US and international patents and patent applications, assigned to Cambridge. Positioning Systems including WO2009112293, WO2008119635, WO2007113086 and US Pat. Pub. No. 2005200525. These disclosed methods and systems are directed at cellular systems, share many of the same limitations as US Pat Pub. No. 2009233621, and have further limitations including limitations on handset (user equipment) characteristics.
The use of SoOPs in navigation presents a very promising solution toward providing a ubiquitous navigation solution in all environments. There are a plethora of RF signals that easily penetrate into what is considered to be a GPS-impaired areas, either due to signal path loss or jamming. Some of these are not only very high power relative to GPS, but offer excellent time resolution to enable precision location due to wide transmission signal bandwidth. Based on the prior art, timing measurement based systems, direction finding systems, and signal power level based measurement systems are all potential candidates. However, power level methods are not considered further due to the variability in power levels and the inability of path loss models to provide robust prediction at such fine resolution, both of which lead to very poor accuracy. Even when calibrated over the coverage areas, accuracy improves, yet is considered to be too constraining due to the fact that it may not feasible to calibrate the area in which navigation is required. Direction finding based systems are considered impractical due to the need for line of sight RF signal reception and the difficulties associated with constructing a miniaturized broad bandwidth phased array antenna system. The present disclosure is directed toward the use of timing-based systems for exploiting SoOPs.
A significant amount of relevant prior art also exists in the field of robotic platform simultaneous location and mapping (SLAM). SLAM is a commonly used technique in autonomous robot navigation systems, where the aim is to self-localize a device while concurrently building a map of the environment around it. In the robotics case, the “map” is a field of stationary objects that surround the robot. The robot traverses through this map and attempts to measure range to each object, either through imaging, laser range finding, or ultrasonics, and continuously updates both the location of the detected objects and its own position, or pose, with respect to the objects. Prior art describes research whereby some of the “objects”, or landmarks, in robotics terminology are RF SoOPs, from which range can be measured through a receiver placed on the robot, Kurth, D., “Range-Only Robot Localization and SLAM with Radio”, Carnegie Mellon University, May 2004. Mathematically, the formulation of this difference lies only in the way the error statistics are modeled within the context of the equations. As an extension of the SLAM navigation concept, Cooperative SLAM, or C-SLAM, is the problem of jointly solving for the location of multiple devices which can communicate with each other who share observation data from SoOP landmarks, detected stationary objects, and of each other.
The basis of SLAM lies in the fundamental theory behind Extended Kalman Filtering (EKF), which is briefly described here. The Extended Kalman Filter linearizes the estimation around the current estimate (similar to a Taylor series expansion) using partial derivatives of the process and measurement functions which are assumed to be somewhat known. The pose at any given time k, is described by the vector qk, which contains the current 2D position as x and y variables, and the heading, or orientation θ.qk=[xk, yk, θk]T  []
The pose at the next time step k+1 is described as qk+1, and is a function of the current state q, a process noise wk, and a forcing function uk. The function mapping the observed measurements to the current pose is described by ƒ, and in the case of the EKF, may be a non-linear process.qk+1=ƒ(qk, uk, wk)  [4]The mathematical details behind the EKF are not included in this document, but are readily known by those skilled in the art and is well documented, see Welch, G., Bishop, G., “An Introduction to the Kalman Filter”, TR 95-041, UNC-Chapel Hill, Jul. 24, 2006. Instead the discussion is limited to key differences between EKF and C-SLAM. C-SLAM is a fairly straightforward extension of the EKF as described. Now, the state vector is modified to include not only the pose of each device, but the position of each landmark as shown below:qk,n=[xk,n, yk,n, θk,n, xla, yla, xlb, ylb, . . . xlM, ylM ]T  [5]Where n is the nth device, and the M landmarks are described by xla, yla, . . . xlM, ylM. The corresponding Jacobian process matrix, another critical distinction between EKF and SLAM is described as:
                                                                        A                ⁡                                  (                                      k                    +                    1                                    )                                            =                                                                    ∂                    h                                                        ∂                    q                                                  ⁢                                  |                                      q                    =                                                                  q                        ^                                            k                                                                                                                                              =                              [                                                                            1                                                              0                                                                                                                -                          Δ                                                ⁢                                                                                                  ⁢                                                  D                          k                                                ⁢                                                  cos                          ⁡                                                      (                                                          θ                              k                                                        )                                                                                                                                      0                                                              0                                                              …                                                              0                                                              0                                                                                                  0                                                              1                                                                                      Δ                        ⁢                                                                                                  ⁢                                                  D                          k                                                ⁢                                                  sin                          ⁡                                                      (                                                          θ                              k                                                        )                                                                                                                                      0                                                              0                                                              …                                                              0                                                              0                                                                                                  0                                                              0                                                              1                                                              0                                                              0                                                              …                                                              0                                                              0                                                                                                  0                                                              0                                                              0                                                              1                                                              1                                                              …                                                              0                                                              0                                                                                                  ⋮                                                              ⋮                                                              ⋮                                                              ⋮                                                              ⋮                                                              ⋮                                                              ⋮                                                              ⋮                                                                                                  0                                                              0                                                              0                                                              0                                                              0                                                              …                                                              1                                                              1                                                                      ]                                                                        [        6        ]            
A significant amount of relevant prior art also exists in the field of RF communication systems & platforms. The prior art includes incremental developments and improvements in point to point radio links in terms of reliability and bandwidth, and the progression towards mobile operation. The prior art also describes “infrastructure architectures”, where mobile nodes or agents (nodes and agents are used interchangeably in this disclosure) communicate with fixed based stations, best illustrated by current cellular communications networks. The prior art also describes extension to infrastructure architectures called “ad hoc architectures”, where nodes communicate directly with each other without the need for base stations. Most recently, a great deal of art has been dedicated to enhancements to ad hoc architectures supporting mobile nodes, and self-organizing/self-healing ad hoc architecture capabilities.
Industry and academic SLAM research has been heavily focused on image processing methods to enable data association for physical object landmark extraction and identification. This is also usually coupled with some sort of ranging mechanism using ultrasonics or laser scanners, and with odometry measurements through optical encoders, inertial navigation sensors, gyroscopes, dead-reckoning, etc. What remains very sparsely researched is the concept of coupling SLAM with radio frequency signals as the ranging measurement source. Entirely absent from any known SLAM research is the concept of using unsynchronized SoOPs paired with SLAM methods in a networked agent scenario.
A significant amount of relevant prior art also exists in the field of software defined radio receivers (SDR) and advanced sensors and platforms. This art describes how a radio receiver can be implemented such that it can be configured to receive and process a wide variety of radio signal types over a wide RF bandwidth in an efficient and cost effective package.
Rapid technological advances have also been made in the area of sensors and platforms, including through increasingly miniaturized electronic components such as MEMS based solid-state gyroscopes, accelerometers, and magnetometers. This technology has been propelled forward by main-stream demands such as the iPhone and household video-gaming controls. Powerful, low-power CPUs with sophisticated power management are fueled by demand for portable computing in smart-phones and laptops. High-density lithium-ion battery technology has been similarly advanced to power these mobile devices. Low-cost CCD cameras are now commodities in most cellular phones and laptops, making imaging technology a possibility for the first time ever for the subject low-cost munitions application. Ultra-compact, low-cost, high-performance multi-band RF transceiver technology has been propelled by demand for high-speed commercial mobile cell phones. Secure, high-speed, IP-based packet data communications have been similarly advanced through a plethora of commodity Wi-Fi enabled devices.
The previously described geolocation and navigation systems and methods use pre-selected RF signal sources with known attributes, locations and relative timing; and they depend on apriori knowledge of existence, attributes and transmitter location of radio signals to be used. Further, they generally operate based on point to point or “infrastructure architecture” communications networks, and utilize conventional receiver architectures and hardware bases. These characteristics limit their ability to utilize the maximum number of measurement sources and measurements which result in a less available and accurate geolocation and navigation solution.
The present disclosure is directed to a novel system and method to allow a more available and accurate geolocation and navigation solution. It utilizes measurements from a heterogeneous mix of apriori known and/or unknown, synchronized and/or unsynchronized, located and/or un-located RF sources (measurements of opportunity), captured by multiple cooperating networked nodes, to render a more robust location solution with respect to availability, accuracy and jamming/spoofing resistance.